home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / glibc108.zip / glibc108 / sysdeps / sparc / divrem.m4 < prev    next >
Text File  |  1993-05-12  |  6KB  |  233 lines
  1. /*
  2.  * Division and remainder, from Appendix E of the Sparc Version 8
  3.  * Architecture Manual, with fixes from Gordon Irlam.
  4.  */
  5.  
  6. /*
  7.  * Input: dividend and divisor in %o0 and %o1 respectively.
  8.  *
  9.  * m4 parameters:
  10.  *  NAME    name of function to generate
  11.  *  OP        OP=div => %o0 / %o1; OP=rem => %o0 % %o1
  12.  *  S        S=true => signed; S=false => unsigned
  13.  *
  14.  * Algorithm parameters:
  15.  *  N        how many bits per iteration we try to get (4)
  16.  *  WORDSIZE    total number of bits (32)
  17.  *
  18.  * Derived constants:
  19.  *  TOPBITS    number of bits in the top `decade' of a number
  20.  *
  21.  * Important variables:
  22.  *  Q        the partial quotient under development (initially 0)
  23.  *  R        the remainder so far, initially the dividend
  24.  *  ITER    number of main division loop iterations required;
  25.  *        equal to ceil(log2(quotient) / N).  Note that this
  26.  *        is the log base (2^N) of the quotient.
  27.  *  V        the current comparand, initially divisor*2^(ITER*N-1)
  28.  *
  29.  * Cost:
  30.  *  Current estimate for non-large dividend is
  31.  *    ceil(log2(quotient) / N) * (10 + 7N/2) + C
  32.  *  A large dividend is one greater than 2^(31-TOPBITS) and takes a
  33.  *  different path, as the upper bits of the quotient must be developed
  34.  *  one bit at a time.
  35.  */
  36.  
  37. define(N, `4')dnl
  38. define(WORDSIZE, `32')dnl
  39. define(TOPBITS, eval(WORDSIZE - N*((WORDSIZE-1)/N)))dnl
  40. dnl
  41. define(dividend, `%o0')dnl
  42. define(divisor, `%o1')dnl
  43. define(Q, `%o2')dnl
  44. define(R, `%o3')dnl
  45. define(ITER, `%o4')dnl
  46. define(V, `%o5')dnl
  47. dnl
  48. dnl m4 reminder: ifelse(a,b,c,d) => if a is b, then c, else d
  49. define(T, `%g1')dnl
  50. define(SC, `%g7')dnl
  51. ifelse(S, `true', `define(SIGN, `%g6')')dnl
  52.  
  53. dnl
  54. dnl This is the recursive definition for developing quotient digits.
  55. dnl
  56. dnl Parameters:
  57. dnl  $1    the current depth, 1 <= $1 <= N
  58. dnl  $2    the current accumulation of quotient bits
  59. dnl  N    max depth
  60. dnl
  61. dnl We add a new bit to $2 and either recurse or insert the bits in
  62. dnl the quotient.  R, Q, and V are inputs and outputs as defined above;
  63. dnl the condition codes are expected to reflect the input R, and are
  64. dnl modified to reflect the output R.
  65. dnl
  66. define(DEVELOP_QUOTIENT_BITS,
  67. `    ! depth $1, accumulated bits $2
  68.     bl    L.$1.eval(2^N+$2)
  69.     srl    V,1,V
  70.     ! remainder is positive
  71.     subcc    R,V,R
  72.     ifelse($1, N,
  73.     `    b    9f
  74.         add    Q, ($2*2+1), Q
  75.     ', `    DEVELOP_QUOTIENT_BITS(incr($1), `eval(2*$2+1)')')
  76. L.$1.eval(2^N+$2):
  77.     ! remainder is negative
  78.     addcc    R,V,R
  79.     ifelse($1, N,
  80.     `    b    9f
  81.         add    Q, ($2*2-1), Q
  82.     ', `    DEVELOP_QUOTIENT_BITS(incr($1), `eval(2*$2-1)')')
  83.     ifelse($1, 1, `9:')')dnl
  84.  
  85. #include "DEFS.h"
  86. #ifdef __svr4__
  87. #include <sys/trap.h>
  88. #else
  89. #include <machine/trap.h>
  90. #endif
  91.  
  92. FUNC(NAME)
  93. ifelse(S, `true',
  94. `    ! compute sign of result; if neither is negative, no problem
  95.     orcc    divisor, dividend, %g0    ! either negative?
  96.     bge    2f            ! no, go do the divide
  97.     xor    divisor, dividend, SIGN    ! compute sign in any case
  98.     tst    divisor
  99.     bge    1f
  100.     tst    dividend
  101.     ! divisor is definitely negative; dividend might also be negative
  102.     bge    2f            ! if dividend not negative...
  103.     sub    %g0, divisor, divisor    ! in any case, make divisor nonneg
  104. 1:    ! dividend is negative, divisor is nonnegative
  105.     sub    %g0, dividend, dividend    ! make dividend nonnegative
  106. 2:
  107. ')
  108.     ! Ready to divide.  Compute size of quotient; scale comparand.
  109.     orcc    divisor, %g0, V
  110.     bne    1f
  111.     mov    dividend, R
  112.  
  113.         ! Divide by zero trap.  If it returns, return 0 (about as
  114.         ! wrong as possible, but that is what SunOS does...).
  115.         ta    ST_DIV0
  116.         retl
  117.         clr    %o0
  118.  
  119. 1:
  120.     cmp    R, V            ! if divisor exceeds dividend, done
  121.     blu    Lgot_result        ! (and algorithm fails otherwise)
  122.     clr    Q
  123.     sethi    %hi(1 << (WORDSIZE - TOPBITS - 1)), T
  124.     cmp    R, T
  125.     blu    Lnot_really_big
  126.     clr    ITER
  127.  
  128.     ! `Here the dividend is >= 2^(31-N) or so.  We must be careful here,
  129.     ! as our usual N-at-a-shot divide step will cause overflow and havoc.
  130.     ! The number of bits in the result here is N*ITER+SC, where SC <= N.
  131.     ! Compute ITER in an unorthodox manner: know we need to shift V into
  132.     ! the top decade: so do not even bother to compare to R.'
  133.     1:
  134.         cmp    V, T
  135.         bgeu    3f
  136.         mov    1, SC
  137.         sll    V, N, V
  138.         b    1b
  139.         add    ITER, 1, ITER
  140.  
  141.     ! Now compute SC.
  142.     2:    addcc    V, V, V
  143.         bcc    Lnot_too_big
  144.         add    SC, 1, SC
  145.  
  146.         ! We get here if the divisor overflowed while shifting.
  147.         ! This means that R has the high-order bit set.
  148.         ! Restore V and subtract from R.
  149.         sll    T, TOPBITS, T    ! high order bit
  150.         srl    V, 1, V        ! rest of V
  151.         add    V, T, V
  152.         b    Ldo_single_div
  153.         sub    SC, 1, SC
  154.  
  155.     Lnot_too_big:
  156.     3:    cmp    V, R
  157.         blu    2b
  158.         nop
  159.         be    Ldo_single_div
  160.         nop
  161.     /* NB: these are commented out in the V8-Sparc manual as well */
  162.     /* (I do not understand this) */
  163.     ! V > R: went too far: back up 1 step
  164.     !    srl    V, 1, V
  165.     !    dec    SC
  166.     ! do single-bit divide steps
  167.     !
  168.     ! We have to be careful here.  We know that R >= V, so we can do the
  169.     ! first divide step without thinking.  BUT, the others are conditional,
  170.     ! and are only done if R >= 0.  Because both R and V may have the high-
  171.     ! order bit set in the first step, just falling into the regular
  172.     ! division loop will mess up the first time around.
  173.     ! So we unroll slightly...
  174.     Ldo_single_div:
  175.         subcc    SC, 1, SC
  176.         bl    Lend_regular_divide
  177.         nop
  178.         sub    R, V, R
  179.         mov    1, Q
  180.         b    Lend_single_divloop
  181.         nop
  182.     Lsingle_divloop:
  183.         sll    Q, 1, Q
  184.         bl    1f
  185.         srl    V, 1, V
  186.         ! R >= 0
  187.         sub    R, V, R
  188.         b    2f
  189.         add    Q, 1, Q
  190.     1:    ! R < 0
  191.         add    R, V, R
  192.         sub    Q, 1, Q
  193.     2:
  194.     Lend_single_divloop:
  195.         subcc    SC, 1, SC
  196.         bge    Lsingle_divloop
  197.         tst    R
  198.         b,a    Lend_regular_divide
  199.  
  200. Lnot_really_big:
  201. 1:
  202.     sll    V, N, V
  203.     cmp    V, R
  204.     bleu    1b
  205.     addcc    ITER, 1, ITER
  206.     be    Lgot_result
  207.     sub    ITER, 1, ITER
  208.  
  209.     tst    R    ! set up for initial iteration
  210. Ldivloop:
  211.     sll    Q, N, Q
  212.     DEVELOP_QUOTIENT_BITS(1, 0)
  213. Lend_regular_divide:
  214.     subcc    ITER, 1, ITER
  215.     bge    Ldivloop
  216.     tst    R
  217.     bl,a    Lgot_result
  218.     ! non-restoring fixup here (one instruction only!)
  219. ifelse(OP, `div',
  220. `    sub    Q, 1, Q
  221. ', `    add    R, divisor, R
  222. ')
  223.  
  224. Lgot_result:
  225. ifelse(S, `true',
  226. `    ! check to see if answer should be < 0
  227.     tst    SIGN
  228.     bl,a    1f
  229.     ifelse(OP, `div', `sub %g0, Q, Q', `sub %g0, R, R')
  230. 1:')
  231.     retl
  232.     ifelse(OP, `div', `mov Q, %o0', `mov R, %o0')
  233.